package com.ronz.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 递归-迷宫问题
 *              约定迷宫规则如下：
 *                  - 0 代表此格子没走过
 *                  - 1 代表此格子为墙
 *                  - 2 代表此格子可走通
 *                  - 3 代表此格子已经走过，但是走不通
 * @Author Ronz
 * @Date 2021/1/2 18:58
 * @Version 1.0
 */
public class No2_Recursion_Maze {

    private static final int row = 8;
    private static final int col = 7;

    public static void main(String[] args) {
        // 创建一个 8 行 7 列的迷宫
        int[][] maze = new int[row][col];
        // 初始化迷宫
        setMaze(maze);
        showMaze(maze);

        System.out.println("=========【下右上左】递归走迷宫==========");
        setWay(maze, 1, 1);
        showMaze(maze);

        maze = new int[row][col];
        setMaze(maze);
        System.out.println("=========【上右下左】递归走迷宫==========");
        setWay2(maze, 1, 1);
        showMaze(maze);
    }


    /**
     * @Description 初始化迷宫
     * @Param [maze]
     */
    public static void setMaze(int[][] maze){
        // 第一行和第八行都是 1
        for (int i=0; i<col; i++){
            maze[0][i] = 1;
            maze[7][i] = 1;
        }

        // 第一列和第七列也都是 1
        for (int i=0; i<row; i++){
            maze[i][0] = 1;
            maze[i][6] = 1;
        }

        // 第四行第二列和第四行第三列都是 1
        maze[3][1] = 1;
        maze[3][2] = 1;
    }

    /**
     * @Description 小球从坐标 maze[1][1] 开始，采用 下、右、上、左 策略来走迷宫
     * @Param [maze, i, j] maze:迷宫      i：当前所处行     j：当前所处列
     * @return boolean
     */
    public static boolean setWay(int[][] maze, int i, int j){
        // 1. 递归结束条件：当迷宫出口被置为 2 时，也即说明小球走到了这个格子
        if (maze[6][5] == 2){
            return true;
        }else{
            // 2. 如果不满足递归结束条件，继续递归
            if (maze[i][j] == 0){   // 如果没走过这个格子
                maze[i][j] = 2;     // 假设这个格子之后能走通
                if (setWay(maze, i+1, j)){  // 先向下走
                    return true;
                }else if (setWay(maze, i, j+1)){    // 如果向下走不通，就向右走
                    return true;
                }else if (setWay(maze, i-1, j)){    // 如果向右走不通，就向上走
                    return true;
                }else if (setWay(maze, i, j-1)){    // 如果向上走不通，就向左走
                    return true;
                }else{  // 如果上下左右都走不通，就说明这个格子是死路
                    maze[i][j] = 3;
                    return false;
                }
            }else{  // 如果这个格子是 1/2/3，由于这里没有回溯算法，就说明走不出去了
                return false;
            }
        }
    }

    /**
     * @Description 小球从 maze[1][1] 开始，采用上、右、下、左策略走迷宫
     * @Param [maze, i, j]
     * @return boolean
     */
    public static boolean setWay2(int[][] maze, int i, int j){
        // 1. 递归结束条件：当迷宫出口被置为 2 时，也即说明小球走到了这个格子
        if (maze[6][5] == 2){
            return true;
        }else {
            // 2. 如果不满足递归结束条件，继续递归
            if (maze[i][j] == 0) {   // 如果没走过这个格子
                maze[i][j] = 2;     // 假设这个格子之后能走通
                if (setWay2(maze, i-1, j)) {  // 先向上走
                    return true;
                } else if (setWay2(maze, i, j+1)) {    // 如果向上走不通，就向右走
                    return true;
                } else if (setWay2(maze, i+1, j)) {    // 如果向右不通，就向下走
                    return true;
                } else if (setWay2(maze, i, j-1)) {    // 如果向下走不通，就向左走
                    return true;
                } else {  // 如果上下左右都走不通，就说明这个格子是死路
                    maze[i][j] = 3;
                    return false;
                }
            } else {  // 如果这个格子是 1/2/3，由于这里没有回溯算法，就说明走不出去了
                return false;

            }
        }
    }

    /**
     * @Description 显示迷宫状态
     * @Param [maze]
     * @return void
     */
    public static void showMaze(int[][] maze){
        // 打印初始迷宫
        for (int i=0; i<row; i++){
            for (int j=0; j<col; j++){
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }

}
